package com.study.leetcode;

import org.junit.Test;

/**
 * @author Honglixi
 * @create 2021-03-21 22:54
 */
public class leetcode206 {
    @Test
    public void testReverseList() {
        System.out.println("testReverseList");
        ListNode head = new ListNode(1);//创建头节点
        head.next = new ListNode(2);//再定义头节点的next域
        ListNode t = head.next;
        for(int i=3;i<10;i++) {//创建一个简单的链表{1,2,3,4,5,...,9}
            t.next = new ListNode(i);
            t = t.next;
        }
        ListNode newHead = t.reverseList(head);//调用反转链表方法
        System.out.println(newHead.val);//检查新的头节点的值
//        printListNode(newHead);//打印新链表的全部节点
    }
    //为了便于查看结果，写的打印链表的方法
    public void printListNode(ListNode head) {
        while(head!=null) {
            System.out.print(head.val+" ");
            head = head.next;
        }
    }

}

class ListNode {
     int val;
     ListNode next;
     ListNode() {

     }
     ListNode(int val) {
         this.val = val;
     }
    ListNode(int val, ListNode next) {
         this.val = val; this.next = next;
     }
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }
}